package Demo2;

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board string字符串一维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    public boolean exist (String[] board, String word) {
        // write code here
        Queue<int[]> queue = new LinkedList<>();
        int n = board.length,m = board[0].length();
        // 将与字符串开头相同的字母的下标放入到队列中
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i].charAt(j) == word.charAt(0)) {
                    queue.add(new int[] {i,j});
                }
            }
        }
        while(!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0], y = tmp[1];
            int index = 1;
            boolean[][] check = new boolean[n][m];
            while(index < word.length()) {
                for(int i = 0; i < 4; i++) {
                    if(check[x][y] == false && (x+dx[i] >= 0 && x+dx[i] < n && y+dy[i] >= 0 && y+dy[i] < m) && board[x+dx[i]].charAt(y+dy[i]) == word.charAt(index)) {
                        check[x][y] = true;
                        x = x+dx[i];
                        y = y+dy[i];
                        break;
                    }
                }
                if(check[x][y] == false && word.charAt(index) == board[x].charAt(y)) {
                    index++;
                }else {
                    break;
                }
            }
            if(index == word.length()) {
                return true;
            }
        }
        return false;
    }
}
class Dmeo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        boolean exist = solution.exist(new String[] {"XYZE","SFZS","XDEE"}, "XYZY");
        System.out.println(exist);
    }
}